package 栈;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class No145二叉树的后序遍历 {

    /**
     * 先吃左右再吃自己(注意到底部再吃)
     * 自研写法
     */
    public static List<Integer> postorderTraversal(TreeNode root) {

        TreeNode thisNode=root;
        Stack<TreeNode> stack=new Stack<>();
        Set<TreeNode> set=new HashSet<>();
        List<Integer> list=new ArrayList<>();

        //左右中 当然是先一直到左 吃掉然后再看右边
        while (!stack.isEmpty()||thisNode!=null){

            if(thisNode!=null){
                stack.add(thisNode);
                thisNode=thisNode.left;//一直吃到最左边
            }else{
                //走到这里说明左边已经吞完了,现在去看栈里的
                thisNode = stack.peek();
                //再去看右边是否为空 或者 是否已经吃过
                if(thisNode.right==null||set.contains(thisNode.right)){
                    list.add(thisNode.val);//吃掉左边先
                    stack.pop();
                    set.add(thisNode);
                    thisNode=null;
                }else
                    thisNode=thisNode.right;//去遍历吃右边的节点

            }

        }

        return list;

    }

    /**
     * 参照写法
     */
    public static List<Integer> postorderTraversalGood(TreeNode root) {

        TreeNode thisNode = root;
        TreeNode r = null;
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode>stack = new Stack<>();
        Set<TreeNode> set=new HashSet<>();
        while(!stack.isEmpty() || thisNode != null)
        {
            if(thisNode != null)
            {
                //一直往左
                stack.push(thisNode);
                thisNode = thisNode.left;
            }
            else
            {
                /**
                 * 思想:一直吃左节点到底部,然后再去遍历底部节点的右节点
                 * 但是当底部节点的右节点为空时,或者右节点已经吃过时,就吃点本身节点
                 * 记得吃完后要重新去栈中拿元素
                 */
                //往左到了尽头
                thisNode = stack.peek();//取出最后一个左
                //发现此节点的右节点已经吃过了,那么就不要再去吃右节点了,直接把自己吃了
                if(thisNode.right == null || set.contains(thisNode.right))
                {
                    //单独一个节点,无右节点||
                    list.add(thisNode.val);//加入
                    set.add(thisNode);//保存吐出的节点,不吃回头草
                    stack.pop();//吐出左右遍历完的b
                    //等于null是为了让它去吐出下一个.因为当前节点的左右已经没了,如果不为null,stack会一直push此节点
                    thisNode = null;
                }
                else//去遍历右节点
                    thisNode = thisNode.right;
            }

        }

        return list;
    }

    public static void main(String[] args) {
        List<Integer> list = postorderTraversal(TreeNode.getNode());
        System.out.println(JSON.toJSONString(list));
    }

}
